#include "findvigenerekeylenght.h"

#include <QHash>
#include <qmath.h>
#include <QtDebug>

#define KASISKI_MATCH_LENGHT 3
#define KASISKI_TOLERANCE 0.01

FindVigenereKeyLenght::FindVigenereKeyLenght(QByteArray input, QByteArray alphabet, int maxLenght, QObject *parent)
    : QThread(parent), input(input), alphabet(alphabet), maxLenght(maxLenght), useFriedman(false)
{}

FindVigenereKeyLenght::FindVigenereKeyLenght(QByteArray input, QByteArray alphabet, QList<qreal> langFreqs, bool trustFriedman, QObject *parent)
    : QThread(parent), input(input), alphabet(alphabet), maxLenght(0), langFreqs(langFreqs), useFriedman(true), trustFriedman(trustFriedman)
{}

void FindVigenereKeyLenght::run()
{
    int size = input.size();
    if (useFriedman)
    {
        qreal kappa_plaintext = 0;
        foreach (qreal f, langFreqs) {
            kappa_plaintext += f*f;
        }
        qreal kappa_random = 1.0/alphabet.size();
        qreal kappa_observed = 0;
        foreach (char c, alphabet) {
            int f = input.count(c);
            kappa_observed += f*(f-1);
        }
        kappa_observed /= size*(size-1);

        qreal friedmanEstimate = (kappa_observed - kappa_random == 0) ?
                    0 : ((kappa_plaintext - kappa_random) / (kappa_observed - kappa_random));
        qDebug() << "Friedman says:" << friedmanEstimate;

        int candidateLenght = qRound(friedmanEstimate);
        if (trustFriedman && candidateLenght > 0)
        {
            qDebug() << "(trust friedman)";
            emit done(candidateLenght);
            return;
        }
        bool nextLenghtIsHigher = friedmanEstimate > candidateLenght;
        int lenghtOffset = 1;

        while(candidateLenght > 0) {
            //find the key lenght
            QList<QHash<char, int> > counts;
            counts.clear();
            QList<qreal> ioc;
            for (int i = 0; i < candidateLenght; i++)
            {
                counts << QHash<char, int>();
            }

            for (int i = 0; i < size; i++)
                counts[i % candidateLenght][input[i]]++;

            ioc.clear();
            QHash<char, int> count;
            foreach (count, counts)
            {
                qreal kappa_parziale = 0;
                int somma = 0;
                foreach (int f, count) {
                    kappa_parziale += f*(f-1);
                    somma += f;
                }
                kappa_parziale /= somma * (somma - 1);
                ioc << kappa_parziale;
            }
            //media
            qreal avg = 0;
            foreach (qreal v, ioc) avg += v;
            avg /= ioc.size();

            if (avg > (kappa_plaintext + kappa_observed) / 2)
            {
                qDebug() << "friedman wins:" << candidateLenght;
                emit done(candidateLenght);
                return;
            }

            candidateLenght += lenghtOffset*(nextLenghtIsHigher?1:-1);
            lenghtOffset++;
            nextLenghtIsHigher = !nextLenghtIsHigher;
        }
        //se arriva qui non ha trovato niente in un range [1, 2*friedmanEstimate)
        //oppure il test di Friedman ha dato risultati non validi (<= 0)
        maxLenght = 0;//lenghtOffset; //circa 2*friedmanEstimate. non basta
    }

    //fallback: kasiski
    if (maxLenght <= 0) maxLenght = qRound(qSqrt(size));
    QList<int> kasiski;
    QList<int> coincidenze;
    for (int i = 0; i <= maxLenght; i++)
    {
        kasiski << 0;
        coincidenze << 0;
    }

    for (int i = 0; i < size; i++)
    {
        for (int j = i + 1; j < size && j <= i + maxLenght; j++)
        {
            int common = commonByteArraySubString(input.mid(i), input.mid(j));
            if (common > 0) coincidenze[j - i]++;
            if (common >= KASISKI_MATCH_LENGHT) kasiski[j - i]++;
        }
    }

    //le coincidenze valgono anche per i divisori
    int totalKCount = 0;
    for (int i = 1; i < kasiski.size(); i++)
    {
        totalKCount += kasiski[i];
        for (int d = 1; d < i; d++)
            if (i % d == 0) kasiski[d] += kasiski[i];
    }
    int candidateLenght = 0;
    for (int i = 1; i < kasiski.size(); i++)
        if (kasiski[i] > totalKCount*(1 - KASISKI_TOLERANCE))
            candidateLenght = i;
    if (candidateLenght > 1)
    {
        qDebug() << "Kasiski wins:" << candidateLenght;
        emit done(candidateLenght);
    }
    else
    {
        // analisi indici di coincidenza
        qreal avg = 0;
        foreach (int v, coincidenze) avg += v;
        avg /= coincidenze.size();
        int maxPos = 0, max = coincidenze[0];
        for (int i = 1; i < coincidenze.size(); i++)
            if (coincidenze[i] > max)
            {
                max = coincidenze[i];
                maxPos = i;
            }
        //TODO find better algorithm
        //
        QList<int> maxList;
        for (int i = 1; i < coincidenze.size() - 1; i++)
            if (coincidenze[i] > avg
                    && coincidenze[i] > coincidenze[i-1]
                    && coincidenze[i] > coincidenze[i+1])
                maxList << i;
        QHash<int, int> distances;
        for (int i = 1; i < maxList.size(); i++)
            distances[maxList[i] - maxList[i-1]]++;
        candidateLenght = 0;
        max = 0;
        foreach (int d, distances.keys())
            if (distances[d] > max)
            {
                max = distances[d];
                candidateLenght = d;
            }
        qDebug() << "coincidenze:" << coincidenze;
        if (candidateLenght > 0 && maxPos % candidateLenght == 0)
        {
            qDebug() << "lunnghrzza probabile:" << candidateLenght;
            emit done(candidateLenght);
        }
        else emit done(coincidenze); //FAIL
    }
}

int FindVigenereKeyLenght::commonByteArraySubString(QByteArray b1, QByteArray b2)
{
    int i = 0;
    int s = qMin(b1.size(), b2.size());
    while (i <= s && b1[i] == b2[i]) i++;
    return i;
}
